package com.peng.leetcode.tree;

/**
 * PathSum3
 * 437. 路径总和 III
 * https://leetcode.cn/problems/path-sum-iii/
 * <p>
 * Created on 2022/12/3
 *
 * @author lupeng
 */
public class PathSum3 {

    public static void main(String[] args) {
        TreeNode root = TreeMain.array2tree(new Integer[]{1000000000, 1000000000, null, 294967296, null, 1000000000, null, 1000000000, null, 1000000000});
        System.out.println(new PathSum3().pathSum(root, 0));
    }

    int ans = 0;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        dfs(root, targetSum);
        return ans;
    }

    void dfs(TreeNode r, int target) {
        if (r == null) {
            return;
        }
        judge(r, target);
        dfs(r.left, target);
        dfs(r.right, target);
    }


    void judge(TreeNode r, long target) {
        if (r == null) {
            return;
        }
        target -= r.val;
        if (target == 0) {
            ans++;
        }
        judge(r.left, target);
        judge(r.right, target);
    }
}
